//
//  main.c
//  005--爬楼梯
//
//  Created by Shawn Li on 2020/5/12.
//  Copyright © 2020 Shawn. All rights reserved.
//

#include <stdio.h>
#include "stdlib.h"

//斐波那契数列的应用

//递归算法
int fibonacci_1(int n){
    if (n < 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    if (n == 2) {
        return 2;
    }
    
    return fibonacci_1(n-1) + fibonacci_1(n-2);
}

//动态规划算法
int fibonacci_2(int n){
    if (n < 1) {
        return 0;
    }
    if (n == 1) {
        return 1;
    }
    int *sum = (int *)malloc(sizeof(int) * (n+1));
    sum[0] = 0;
    sum[1] = 1;
    sum[2] = 2;
    for (int i = 3; i <= n; i++) {
        sum[i] = sum[i-1] + sum[i-2];
    }
    return sum[n];
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    int testNum = 5;
    for (int i = 0; i < testNum + 1; i++) {
        printf("%d\n", fibonacci_2(i));
    }
//    printf("%d\n", fibonacci_1(5));
    return 0;
}
